package baseclass.j_dp.dp;

import java.util.Arrays;

/**
 * 给定一个二维数组m行，n列。假设这个二维数组中每个单元格的值都是正整数，
 *
 * 表示从该单元格经过时需要花费的成本。
 *
 * 那么求从右上角第一个单元格到右下角最后一个单元格的路径中，花费的最小成本是多少？
 *
 * 约束条件为：你只能向右，向下，或者向右下（对角线方向）走。
 * @date 2020/3/1 21:06
 */
public class Code01_MinMatrixPath {

    /**
     * 方式1：从(0,0)开始回溯
     */
    public static int minWalk1(int[][] matrix, int i, int j) {
        if(matrix == null || matrix.length == 0) return 0;
        return doWork1(matrix,0,0,matrix.length-1,matrix[0].length-1);
    }

    private static int doWork1(int[][] matrix, int i, int j, int row, int col) {
        //终点
        if(i == row && j == col){
            return matrix[row][col];
        }
        //最后一行
        if(i == row){
            return matrix[i][j] + doWork1(matrix,i,j+1,row,col);
        }
        //最后一列
        if(j == col){
            return matrix[i][j] + doWork1(matrix,i+1,j,row,col);
        }
        //否则选择下或右最小
        return matrix[i][j] + Math.min(doWork1(matrix,i+1,j,row,col),
                doWork1(matrix,i,j+1,row,col));
    }
    /**
     * 方式2：从(0,0)开始回溯，对方式1进行缓存。
     * 可以用一个二维数组或者是Map缓存。
     * cache(i,j)代表从(i,j)到达终点的最优解。
     */
    public static int minWalk2(int[][] matrix, int i, int j) {
        if(matrix == null || matrix.length == 0) return 0;
        int[][] cache = new int[matrix.length][matrix[0].length];
        for (int k = 0; k < cache.length; k++) {
            Arrays.fill(cache[k],-1);
        }
        return doWork2(matrix,0,0,matrix.length-1,matrix[0].length-1,cache);
    }

    private static int doWork2(int[][] matrix, int i, int j, int row, int col, int[][] cache) {
        //终点
        if(i == row && j == col){
            return matrix[row][col];
        }
        //最后一行
        if(i == row){
            return doProcess(matrix,i,j,cache,0);
        }
        //最后一列
        if(j == col){
            return doProcess(matrix,i,j,cache,1);
        }
        //否则选择下或右最小
        return doProcess(matrix,i,j,cache,2);
    }
    private static int doProcess(int[][]matrix,int i,int j,int[][]cache,int type){
        if(cache[i][j] != -1) return cache[i][j];
        if(type == 0){
            //最后一行
            cache[i][j] = matrix[i][j] +
                    doWork1(matrix,i,j+1,matrix.length-1,matrix[0].length-1);
        }else if(type == 1){
            //最后一列
            cache[i][j] = matrix[i][j] +
                    doWork1(matrix,i+1,j,matrix.length-1,matrix[0].length-1);
        }else {
            cache[i][j] =
                    matrix[i][j] +
                     Math.min(doWork1(matrix,i+1,j,matrix.length-1,matrix[0].length-1),
                      doWork1(matrix,i,j+1,matrix.length-1,matrix[0].length-1));
        }
        return cache[i][j];
    }

    /**
     * 方式3：DP
     */
    public static int minDP(int[][] matrix) {
        if (matrix == null || matrix.length == 0) {
            return 0;
        }
        int row = matrix.length -1;
        int col = matrix[0].length-1;
        int[][] M = new int[row+1][col+1];
        //先填充最后一行和最后一列的最优解
        M[row][col] = matrix[row][col];
        for (int i = col - 1; i >=0 ; i--) {
            M[row][i] = matrix[row][i] + M[row][i+1];
        }
        for (int i = row - 1; i >=0 ; i--) {
            M[i][col] = matrix[i][col] + M[i+1][col];
        }
        //填充其他位置，从后往前从下往上填充
        for (int i = row -1; i >=0 ; i--) {
            for (int j = col-1; j >=0 ; j--) {
                M[i][j] = matrix[i][j] + Math.min(M[i+1][j],M[i][j+1]);
            }
        }
        return M[0][0];
    }

    // for test
    public static int[][] generateRandomMatrix(int rowSize, int colSize) {
        if (rowSize < 0 || colSize < 0) {
            return null;
        }
        int[][] result = new int[rowSize][colSize];
        for (int i = 0; i != result.length; i++) {
            for (int j = 0; j != result[0].length; j++) {
                result[i][j] = (int) (Math.random() * 10);
            }
        }
        return result;
    }


    public static void main(String[] args) {
        int[][] m = {{1, 3, 5, 9}, {8, 1, 3, 4}, {5, 0, 6, 1}, {8, 8, 4, 0}};
        System.out.println(minWalk1(m, 0, 0));
        System.out.println(minWalk2(m, m.length - 1, m[0].length - 1));
        System.out.println("DP");
        System.out.println(minDP(m));

      /*  boolean flag = false;
        for (int i = 0; i < 1000; i++) {
            m = generateRandomMatrix(10, 20);
            if ( minDP(m) != minWalk1(m, 0, 0)){
                System.out.println(m);
                flag = true;
                break;
            }
        }
        System.out.println((flag ==true) ? "错误":"正确");*/
    }
}
